NowCode：HJ32 密码截取

发表于 | 分类于

题目：密码截取

Catcher用一些对称的密码进行通信，比如像这些 “ABBA””ABBA” 、”ABA””ABA” 、”A””A” 、”123321””123321”。
但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 “ABBA”→”12ABBA””ABBA”→”12ABBA” 、”ABA”→”ABAKK””ABA”→”ABAKK”，”123321”→”51233214””123321”→”51233214” 。因为截获的串太长了，而且存在多种可能的情况（ “abaaab””abaaab” 可看作是 “aba””aba” 或 “baaab””baaab” 的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

输入描述：

在一行上输入一个长度为 1≦length(s)≦25001≦length(s)≦2500 ，仅由大小写字母和数字构成的字符串 ss ，代表截获的密码。

输出描述：

在一行上输出一个整数，代表最长的有效密码串的长度。

示例1

1
2
3
4
5
6
7
8
输入：
ABBA

输出：
4

说明：
在这个样例中，没有无关字符，所以最长的有效密码串就是 "ABBA" 本身，长度为 4 。
示例2
1
2
3
4
5
6
7
8
输入：
12HHHHA

输出：
4

说明：
在这个样例中，最长的有效密码串是 "HHHH" ，长度为 4 。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
using namespace std;

int ExpandAroundCenter(const std::string& s, int left, int right) {
    int l = left;
    int r = right;
    int n = s.size();
    while(l >= 0 && r < n && s[l] == s[r]) {
        l--;
        r++;
    }
    // cout << r - l - 1 << endl;
    return r - l - 1;
}

int main() {
    std::string s;
    getline(cin, s);
    int maxLength = 1;
    for (size_t i = 0; i < s.size() - 1; i++) {
        int length1 = ExpandAroundCenter(s, i, i);
        int length2 = ExpandAroundCenter(s, i, i + 1);
        if (length1 > maxLength) {
            maxLength = length1;
        }
        if (length2 > maxLength) {
            maxLength = length2;
        }
    }
    cout << maxLength;

}

思路

题目要求找出最长的回文子串，不管这个子串是在原字符串的中间还是被其他字符包裹。那么，问题转化为找出给定字符串中的最长回文子串的长度。这和经典的“最长回文子串”问题是一样的吗？是的，应该就是这样的。所以解决这个问题的方法应该是如何高效地找到最长的回文子串。

那经典的解法有哪些呢？常见的两种方法：中心扩展法和动态规划。比如，中心扩展法对于每个可能的中心点，向两边扩展，直到不是回文为止。而动态规划则是构建一个二维表格，记录子串是否为回文。